找到一套基数 [英] Find cardinality of set
问题描述
我最近遇到了以下问题：
I have faced the following problem recently:
我们有M个连续整数序列A，开始在A [1] = 1： 1,2，...，M（例如：M = 8，A = 1,2,3,4,5,6,7,8）
We have a sequence A of M consecutive integers, beginning at A[1] = 1: 1,2,...M (example: M = 8 , A = 1,2,3,4,5,6,7,8 )
我们必须集合T由来自L_T连任A.作出一切可能的子序列 （实施例L_T = 3，子序列是{1,2,3}，{2,3,4}，{3,4,5}，...）。让我们致电T砖的元素。
We have the set T consisting of all possible subsequences made from L_T consecutive terms of A. (example L_T = 3 , subsequences are {1,2,3},{2,3,4},{3,4,5},...). Let's call the elements of T "tiles".
我们有集合S包括A具有长度L_S所有可能的子序列。 （例如L_S = 4，如子序列{1,2,3,4}，{1,3,7,8}，... {4,5,7,8}）。
We have the set S consisting of all possible subsequences of A that have length L_S. ( example L_S = 4, subsequences like {1,2,3,4} , {1,3,7,8} ,...{4,5,7,8} ).
我们说一个元s的S可以，如果有T中存在ķ砖覆盖的T K砖，使得自己的电视机方面的工会含有S的一个子集的条款。例如，亚序列{1,2,3}可覆盖2瓦长度2（{1,2}和{3,4}），而subsequnce {1,3,5}是不可能的盖带2砖的长度为2，但可能覆盖与2瓦片长度为3的（{1,2,3}和{4,5,6}）。
We say that an element s of S can be "covered" by K "tiles" of T if there exist K tiles in T such that the union of their sets of terms contains the terms of s as a subset. For example, subsequence {1,2,3} is possible to cover with 2 tiles of length 2 ({1,2} and {3,4}), while subsequnce {1,3,5} is not possible to "cover" with 2 "tiles" of length 2, but is possible to cover with 2 "tiles" of length 3 ({1,2,3} and {4,5,6}).
令C为S的元素，可以覆盖由T. K个瓦片
Let C be the subset of elements of S that can be covered by K tiles of T.
查找的C给出的基数男，L_T，L_S，K。
Find the cardinality of C given M, L_T, L_S, K.
任何想法，将AP preciated如何解决这个问题。
Any ideas would be appreciated how to tackle this problem.
推荐答案
假设 M 是整除 T ，因此，我们有瓦覆盖的初始设置中的所有元素（否则说法目前还不清楚）。的整数倍
Assume M is divisible by T, so that we have an integer number of tiles covering all elements of the initial set (otherwise the statement is currently unclear).
首先，让我们来细数 F（P）：这将是长个子的几乎数量 L_S 它可以精确地所覆盖不超过 P 瓦片，但不是。
从形式上看， F（P）=选择（M / T，P）*选（P * T，L_S）。
我们首先选择完全 P 覆盖瓦片：方法数为选择（M / T，P）。
当砖是固定的，我们有完全 P *牛逼不同的元素可用，并且有选择（P * T，L_S）的方式选择一个序列。
First, let us count F (P): it will be almost the number of subsequences of length L_S which can be covered by no more than P tiles, but not exactly that.
Formally, F (P) = choose (M/T, P) * choose (P*T, L_S).
We start by choosing exactly P covering tiles: the number of ways is choose (M/T, P).
When the tiles are fixed, we have exactly P * T distinct elements available, and there are choose (P*T, L_S) ways to choose a subsequence.
那么，这种方法有一个缺陷。 需要注意的是，当我们选择了一个瓦但在根本不使用它的元素，我们实际上计数一些亚序列一次以上。 举例来说，如果我们固定的三张牌编号为2,6和7，但只用了2和7，我们一次又一次地数着相同的子序列，当我们固定的编号为2,7和一切三个瓷砖
Well, this approach has a flaw. Note that, when we chose a tile but did not use its elements at all, we in fact counted some subsequences more than once. For example, if we fixed three tiles numbered 2, 6 and 7, but used only 2 and 7, we counted the same subsequences again and again when we fixed three tiles numbered 2, 7 and whatever.
上述问题可以通过的排容原理的变化被抵消。
的确，对于一个子只是它使用问：瓷砖了 P 选择瓷砖，就被计数选择（MQ，PQ）次，而不是只有一次：问： 的P 选择是固定的，但其他的都是任意的。
The problem described above can be countered by a variation of the inclusion-exclusion principle.
Indeed, for a subsequence which uses only Q tiles out of P selected tiles, it is counted choose (M-Q, P-Q) times instead of only once: Q of P choices are fixed, but the other ones are arbitrary.
定义 G（P）因为它可以覆盖完全<长度 L_S 的子序列的数量code> P 瓷砖。
然后， F（P）是总和•从0至P 产品 P = 0 向上的工作，我们可以通过计算<$ C $的值计算 G（2）从知道 F（2）， G（ 0）和 G（1），并且还连接式 F（2）与 G（0）， G（1）和 G（2）。
Define G (P) as the number of subsequences of length L_S which can be covered by exactly P tiles.
Then, F (P) is sum for Q from 0 to P of the products G (Q) * choose (M-Q, P-Q).
Working from P = 0 upwards, we can calculate all the values of G by calculating the values of F.
For example, we get G (2) from knowing F (2), G (0) and G (1), and also the equation connecting F (2) with G (0), G (1) and G (2).
在此之后，答案很简单总和对于p从0至K 的值 G（P）
After that, the answer is simply sum for P from 0 to K of the values G (P).
这篇关于找到一套基数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
