For questions about the study of finite or countable discrete structures, specifically how to count or enumerate elements in a set (perhaps of all possibilities) or any subset. It includes questions on permutations, combinations, bijective proofs, and generating functions.

learn more… | top users | synonyms (4)

6
votes
1answer
569 views

How many points of intersection?

Suppose there are $n$ points equally spaced ( i.e. the distances between two consecutive points are same) on the circumference of a circle. Now if we join each point with every other points by a ...
1
vote
3answers
258 views

product of the numbers in each subset is equal [duplicate]

Possible Duplicate: product of six consecutive integers being a perfect square Find all positive integers $n$ such that the set {$n, n + 1, n + 2, n + 3, n + 4, n + 5$} can be ...
3
votes
0answers
75 views

$\mathbb{Z}$-Polynomials in an Enumeration Identity

I've conjectured the following identity: For $1 \leqslant k \leqslant l \leqslant n$ and $m \in \mathbb{N}$, \begin{align} \sum_{1 \leqslant i_1 < \cdots < i_l \leqslant n} i_{k}^{m} = \sum_{j = ...
8
votes
3answers
1k views

“Go-first” dice for $N$ players

I'm interested in sets of dice that can be used to determine who "goes first" (hence the name) in an $N$-player game; more generally, I want to determine a complete ordering of the players with a ...
2
votes
3answers
54 views

combinatorics counting sets with a one element having values in another set

counting the number of ordered subsets in a n-set is easy, it's $ 2 ^n -1 $ (assuming we don"t want the empty subset, it's the sum of $ n \choose i $ , i>0 now imagine I have a set s=(a, b, x), where ...
1
vote
1answer
616 views

How many different postal codes can be assigned?

Every street in Canada is assigned a postal code. A postal code is made up of 3 letters and 3 digits that alternate. How many different postal codes can be created given the following conditions? ...
6
votes
0answers
156 views

Bruhat order and RSK

The RS(K) correspondence is a bijection between elements of the symmetric group $S_n$ and pairs of standard tableaux of the same shape. The symmetric group is partially ordered by the Bruhat order, ...
3
votes
2answers
92 views

Possibly a combinatorial problem

I have a $5 \times 5$ grid as below $$\begin{array}{ccccc} 0& 1& 0& 1& 1\\ 1& 0& 0& 0& 0\\ 1& 0& 0& 0& 0\\ 1& 0& ...
3
votes
1answer
59 views

Convex programming when the problem has an underlying combinatorial structure that's a DAG

I have a nonlinear convex objective function to minimize. The function is defined on a set of variables: $\{ x_1,x_2, \ldots ,x_p \},$ where each $x_i$ is a number associated with a path in the DAG. ...
3
votes
1answer
376 views

Summation Identity for Stirling Numbers of the First Kind

For the Stirling numbers of the second kind, the following identity is well-known: \begin{align} S(n,l) = \sum_{k_1 + \cdots + k_l = n-l} 1^{k_1} 2^{k_2} \cdots l^{k_{l}}, \end{align} where the sum is ...
5
votes
1answer
116 views

Number of specific partitions of a given set

Let U be the set $U=\{(1,2,3,\ldots,2^m)\}$. Let $A$ and $B$ partitions of $U$, such that $A \cup B$ is the set $U$, and their intersection is empty, and adding the elements of the first set is the ...
0
votes
1answer
267 views

Interpretation of the number of non-negative integer solutions to an equation

So assume there are $N$ identical balls to be arranged into $r$ boxes. There could be empty boxes. Howe many ways are there to arrange it? So the text book give an example of solving $N$ identical ...
1
vote
1answer
157 views

How many subsets are there?

I'm having trouble simplifying the expression for how many sets I can possibly have. It's a very specific problem for which the specifics don't actually matter, but for $q$, some power of $2$ greater ...
0
votes
3answers
1k views

How many positive, three-digit integers contain at least one $3$

How many positive, three-digit integers contain at least one $3$ as a digit but do not contain $5$ as a digit? I have an answer for that which is $215$ ,is that right ? If its wrong then ,how to ...
1
vote
2answers
226 views

A combinatorial problem of counting closed walks on grid

Consider an arbitrarily large $N \times N$ grid graph. How can I express the number of closed walks starting from a reference vertex $v$ in terms of the length $L$ of the walk? For example, for $L = ...
2
votes
0answers
91 views

Proving generating functions equality

What do you use to prove the following equality (and possibly more general ones of the kind)? \begin{align*}\sum_{r,s,t} \frac{q^{r^2+rs+s^2+st+t^2}}{(q)_r (q)_s (q)_t} z_1^{r+s} z_2^{s+t} = ...
3
votes
2answers
667 views

Identical balls arrangement in a circle

Six identical yellow balls and four identical red balls are to be arranged in the circumference of a circle. In how many ways it can be done?
4
votes
2answers
157 views

Polynomials and partitions

There is a question I have based on the fact: If you take a quadratic polynomial with integer coefficients, take the set $\{1,2,3,4,5,6,7,8\}$, make a partition $A=\{1,4,6,7\}$, $B=\{2,3,5,8\}$, and ...
0
votes
4answers
240 views

choose n letters to form possible words from m letters, restraint no letter should be used more than twice

Given $m$ letters (distinct letters), choose $n$ ($n < m$) letters to form words (the word doesn't need to be correct), and no letter can be used more than twice. How many distinct word can be ...
1
vote
1answer
288 views

Counting descending sequences of positive integers

The complete question I would like to answer is: Given positive integers $k,n$, how many descending lists of non-negative integers $(x_1~x_2\ldots x_k)$ are there such that $\sum_{i=1}^k x_i = n$? ...
3
votes
2answers
134 views

Sum of Natural Number Ranges?

Given a positive integer $n$, some positive integers $x$ can be represented as follows: $$1 \le i \le j \le n$$ $$x = \sum_{k=i}^{j}k$$ Given $n$ and $x$ determine if it can be represented as the ...
3
votes
5answers
1k views

Counting the ordered pairs $(A, B)$, where $A$ and $B$ are subsets of $S$ and $A$ is a proper subset of $B$:

Let $S$ be a set of $n$ consecutive natural numbers. How to find the number of ordered pairs $(A, B)$, where $A$ and $B$ are subsets of $S$ and $A$ is a proper subset of $B$. The answer in my book $ ...
3
votes
1answer
153 views

Average Maximum Of Random Subset?

Suppose I have a set of $n$ real numbers, $\{x_1, x_2, \dots, x_n\}$. I choose a uniformly random subset of size $m \le n$. What is the expected maximum of the subset in terms of $n$, $m$ and $x_i$? ...
3
votes
2answers
76 views

Prove the following $\tan(nA)$ expansion

I've figured out the approach. Writing the expansion of $(1 + x)^n$, then replacing $x$ with $i \tan (A)$. Then separating real and imaginary part and $\tan(nA)$ will be equal to Im/Real. But, after ...
1
vote
1answer
423 views

length of paths between two nodes in a directed acyclic graph

What might be a good way to calculate length of all paths between two nodes in a directed acyclic graph? I don't need the actual paths, just the length. Is there a combinatorial formula for that?
2
votes
1answer
302 views

Using the Multinomial Theorem to Calculate a Finite Sum raised to an exponent

I know it's a simple question, but I keep getting different general formulas for the coefficients when I am trying to use the multinomial theorem for the following: $$ ...
5
votes
2answers
434 views

What is the shortest sequence that contains every permutation of $1..n$? [duplicate]

Possible Duplicate: What is the shortest string that contains all permutations of an alphabet? How can one create a list of numbers so that by taking $n$ consecutive elements from that ...
3
votes
1answer
2k views

How many words can be formed from the letters of the word 'DAUGHTER' so that the vowels never come together?

How many words can be formed from the letters of the word 'DAUGHTER' so that the vowels never come together ? The answer is obviously $8!-6!\cdot3!$. My question is that if we ponder from a ...
4
votes
2answers
357 views

People being seated around a table refusing to sit next to two other people

I was going to generalize an easy counting problem and I ended up not being able to solve it: In how many ways can $n$ people $1,\dots,n$ be seated around a round table if person $i$ refuses to ...
0
votes
3answers
292 views

Square-root of symmetric square matrices [closed]

I am working with the square-roots of square symmetric matrices. The answers are to be binary symmetric matrices. If we take the matrix $$M = ...
4
votes
6answers
3k views

Arrangement of the word 'Success'

Number of ways the word 'Success' can be arranged, such that no two S's and C's are together.
1
vote
3answers
170 views

Counting number of ways of splitting a card deck

Suppose that we have a $52$-card deck. We are interested to find how many different combinations there could be if we divide this $52$-card deck in two parts, so that in each part there are $2$ aces. ...
3
votes
1answer
89 views

Number of Optional Pairings?

So I need to calculate the number of ways you can partition a set of $n$ items such that the size of each partition is either 1 or 2. Let $m = \lfloor \frac{n}{2}\rfloor$ $m$ is the maximum number ...
9
votes
2answers
435 views

Stirling Numbers of the First Kind - a direct derivation

Usually, the Stirling numbers of the first kind are defined as the coefficients of the rising factorial: $(*) \prod_{i=0}^{n-1}(x+i) = \sum_{i=0}^{n} S(n,i) x^i$. With this definition, a recursive ...
3
votes
1answer
1k views

Multiplication of Two Infinite Series

This question has been deleted. How to prove that $$\displaystyle \left( \sum_{k=0}^{\infty }\frac{\left( -a\right) ^{k}y^{2k}}{k!}\right) \left( \sum_{k=0}^{\infty }\frac{a^{k}y^{2k+1}}{\left( ...
3
votes
2answers
403 views

What was the name of that generalization of “Hall's marriage theorem”?

can sombody help me in graph theory? I just need to know the name of the generalization of Hall's marriage theorem... the one that states that if I have a bipartite graph between set $A$ with $n$ ...
1
vote
1answer
112 views

How many $1$'s could there be in this sequence? Matrix, operator?

For each $(i,j)\in \mathbb{N}^2$, $a(i,j)=1$ or $0$, and 1) $a(i,i)=0$ for all $i$; 2)for fixed $i$, there is at most one $j$ such that $a(i,j)=1$. Suppose we know that there is a finite $\kappa$ such ...
0
votes
1answer
82 views

Combination of n sets that produces a set of n-tuple

Given n sets with 3 elements: $X_i=\{a_i,b_i,c_i\}$ where $\{i\in\mathbb{N}|1\leq i\leq n\}$. How can I define a n-tuple based on combination of this sets that produces the set $S$ with $3^n$ ...
1
vote
2answers
147 views

How can I count partitions of X having N items?

I need to count the possible partitions where sum of it's members is X, but every set has N items. For example X=5 and N=4: { 1,1,1,2 } X=5, N=3: ...
1
vote
1answer
114 views

Whitney numbers of the Divisor Lattice

I'm computing Whitney numbers of the Divisor lattice of an integer $n = \prod_{p \mid n} p^{\text{ord}_{p}(n)} = p_1^{n_1} \cdots p_{q}^{n_{q}}$ using the formula quoted in Erdos and Szekely's ...
4
votes
4answers
6k views

What is the total number of combinations of 5 items together when there are no duplicates?

I have 5 categories - A, B, C, D & E. I want to basically create groups that reflect every single combination of these categories without there being duplicates. So groups would look like this: ...
2
votes
1answer
175 views

Number of blocks in a $t-(v,k,\lambda)$ design having an empty intersection with a given set

Question Given a $t-(v,k,\lambda)$ design $(X,\mathcal{B})$ and a set $U\subset X$ with $|U|=u\leq t$, what is the number of blocks $B\in\mathcal{B}$ such that $B\cap U=\emptyset$? The answer is: ...
5
votes
3answers
3k views

what is the sum of following permutation series $nP0 + nP1 + nP2 +\cdots+ nPn$?

what is the sum of following permutation series $nP0 + nP1 + nP2+\cdots+ nPn$ ? I know that $nC0 + nC1 +\cdots + nCn = 2^n$, but not for permutation. Is there some standard result for this ?
9
votes
2answers
803 views

“Ballot numbers” sum up to Catalan numbers

Summing certain numbers and comparing the results with OEIS, I found that $ \sum_{k=1}^n \frac{k^2}{n} \binom{2n-k-1}{n-1} = C_{n+1} - C_{n}, $ where $C_n$ denotes the $n^{\textrm{th}}$ Catalan ...
1
vote
2answers
118 views

A problem in combinatorics

8 subjects need to be given to 4 students. In how many ways can it be done so that the third student gets an odd number of subjects. I tried combination with repetition $9 \choose 7$+$7 \choose 5$+$5 ...
2
votes
2answers
139 views

How many divisors of a set of numbers has?

Let $S:=\{x_1,x_2,\dots,x_n\}$ be a finite set of natural numbers. Is there an efficient algorithm to find how many numbers divide at least one of $x_i$ in the set $S$? For example. If $S=\{2,6,15\}$ ...
6
votes
2answers
159 views

Sum of squares of multiplicities of differences

It's hard to come up with a good title. Let $A$ be a set of $n$ integers, say $A=\{a_1,\ldots,a_n\}$ with $a_1<\cdots<a_n$. We consider all the positive differences $a_j-a_i$ (necessarily ...
2
votes
0answers
387 views

Probability that a short random string, over an N-letter alphabet, appears 'k' times in a longer random string

I have two random strings over an $N$-letter alphabet: one is a shorter $M$-letter string, and one is a longer $L$-letter string. Assuming that two or more instances of the shorter string can ...
0
votes
1answer
274 views

Conditional Combinations

Asking this question on SO, I have been advised to post it here. I will be using Javascript to implement : Please consider a row of size 12. On that row, I want to place some items that have 3 ...
2
votes
1answer
261 views

How many maximal consistent sets are there on a $\mathscr{FOL}$

Let $\mathfrak L$ be a $\mathscr{FOL}$ with completeness and soundness. My question is how many maximal consistent sets on it? I know that every maximal consistent set can be dealt as an ...