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)

0
votes
1answer
5 views

Reduction from Circuit-Sat to 3-Sat

I'm reading the following notes on reduction from circuit-sat to 3-sat http://www.cs.cmu.edu/~avrim/451f11/lectures/lect1108.pdf On the third page i'm unsure how they arrived at the following In ...
0
votes
0answers
15 views

Proving that $\sum_{i\geq0}f_i(n,m)x^i=\sum_{k=0}^n(-1)^k{n \choose k}\big((1+x)^{n-k}-1\big)^m$

Let $f_i(n,m)$ ($n,m\geq1i\geq0$) be the number of $m\times n$ matrices with entry of 0 and 1, so that there is in each row and column at least one 1 and total exactly i ones. I have to show that: ...
2
votes
0answers
23 views

All clubs have a member among $n$ people

Let $n \geq 14$ be a positive integer. In a city there are more than $n$ clubs, all of them have exactly 14 members. At each group of $n+1$ clubs there is a person who is member of at least 15 of ...
-1
votes
2answers
37 views

How to prove that a map is bijective and how to win the inclusion exclusion theorem

Let $S$ be a set of n elements and $V$ the $2^n$-dimensional vector space of all maps $f : 2^S \to \mathbb{C}$ Let $\phi : V \to V$ be the linear map so that for $f : 2^S \to \mathbb{C}$ the ...
3
votes
0answers
17 views

An infinite sum of polygammas

Please help me with the proof of what follows. $$\sum _{m=0}^{\infty } (z+1)_{-m} \psi (z-m) \prod _{k=0}^m \frac{1}{\psi (z-k+1)}=1$$ The real part of z is not an integer.
3
votes
2answers
33 views

An infinite sum

Can someone help me prove the below? Thanks. $$\sum _{k=1}^{\infty } \frac{\Gamma (k)^2}{\prod _{m=1}^k (x \Gamma (m)+m)}=\frac{1}{x}$$
0
votes
0answers
18 views

Questions on Erdős–Ginzburg–Ziv theorem for primes and understanding related lemmas and their applications.

While trying to prove the prime case of Erdős–Ginzburg–Ziv theorem: Theorem: For every prime number $p$, in any set of $2p-1$ integers, the sum $p$ of them divisible by $p$. I came across with ...
0
votes
1answer
11 views

Combinatorics-Summation doubt in the proof of the expectation of the Hypergeometric distribution.

The proof starts considering this equality: $(d/dx (1+x)^A)(1+x)^B = A(1+x)^{A+B-1}$ Then it keep on changing every $(1+x)^{A or B}$ for its binomial coefficient. That 's what I don't understand. If ...
0
votes
0answers
25 views

estimations in the birthday paradox?

The birthday paradox is the famous following problem: What is the probability $p_n$ that at least $2$ persons amongst $n$ persons chosen at random have the same birthday? Leap years are not taken ...
3
votes
3answers
89 views

Difficult inverse tangent identity

Prove that: $$\arctan\left(\frac{\sqrt{1 + x} - \sqrt{1-x}}{\sqrt{1 + x} + \sqrt{1-x}} \right) = \frac{\pi}{4} - \frac{1}{2}\arccos(x), -\frac{1}{\sqrt{2}} \le x \le 1$$ I'd multiply the ...
2
votes
1answer
21 views

Existence question about Hamming weights of addition of numbers modulo $2^n-1$

Let $w_1, w_2$ be given, $1 \leq w_1 \neq w_2 \leq n-1$. Given an integer $a$, $1 \leq a \leq 2^n-2$, can we find $b$, $1 \leq b \leq 2^n-2$, with $W_H(b) = w_1$ and such that $W_H(a + b \mod{2^n-1}) ...
3
votes
0answers
54 views

Partial sums of falling factorials

I want to know if there exists some way, approximate or exact, to do a partial sum of falling factorials of the kind: $$\sum_{k=i}^{n}(a+k)_{h}$$ where all are constants. And I'm interested too in ...
2
votes
0answers
36 views

Combinatorial express of n^3 [duplicate]

I know following expression $$n = {n\choose 1 } $$ $$n^2 = {n\choose 2 } + {n+1\choose 2 }$$ but how about $n^3 = $? Are there simple expression?
3
votes
2answers
63 views

Computing the $n^{\textrm{th}}$ permutation of bits.

I've seen this post about the $n^{\textrm{th}}$ permutation of a set but that is not what I need. If you have a bit string (ones and zeros only) there are algorithms to quickly permute the NEXT ...
2
votes
1answer
97 views

Impossible Math Riddle [duplicate]

Mathematician A asks Mathematician B to guess the age of his three sons. Mathematician A starts off by giving Mathematician B two clues. The two clues are: The product of their ages is 72. When you ...
0
votes
1answer
33 views

All possible variants of representation natural number N as product of natural numbers

Task : describe a predicate (on Prolog) that count all possible variants of representation of natural number N as product of natural numbers. For example, 6 = 6*1 = 2*3, so answer is 2. The program ...
0
votes
1answer
48 views

How many combinations are there?

I have $4$ electrons to place in $7$ orbitals. Each orbital can hold up to some maximum number of electrons. Let's name the orbitals $a,b,c,d,e,f,g$ for reference. Let's say the maximums are ...
2
votes
2answers
39 views

Probability and Combinatorics without replacement

If I have a sample space of $A$ and I randomly select $a$ elements, mark them, put them back into the sample space, then randomly select $b$ elements and I want to know what the probability is that ...
2
votes
2answers
28 views

Proof that repeated sum equals binomial formula

Let $s, d$ be positive integers. Can you prove the following general formula for the repeated sum? I developed this problem on my own, but is it a well known result? $$\sum_{i_1 = 0}^s \sum_{i_2 = ...
0
votes
1answer
24 views

Multinomial Joint Probability: Red *and* blue balls

Say that there is an urn with balls of different colors. $P(R)$ and $P(B)$ are the probabilities of drawing red or blue balls. These do not add up to one. Say I have $N$ draws (with putting back the ...
1
vote
1answer
21 views

Distributing infinite supply of $n$ distinct objects into $k$ identical urns

I have $n$ distinct objects, namely {$n_{1\le i \le n}$} with an infinite supply of each of them, and I have $k$ identical, indistinguishable urns to place the objects in. Each urn will contain ...
1
vote
0answers
27 views

Solution to a combinatorial constraint system

I am facing a combinatorial problem where I am interested in the minimum number of constraints of a certain type that uniquely determine a solution. I realize that my problem is highly specific (and I ...
0
votes
1answer
29 views

Word problem in linear equation

I just can't figure it out how to solve this one.The problem is as follows: Of 28 students taking at least one subject, the number taking Math and English but not History equals the number ...
1
vote
0answers
10 views

An optimization problem with a simplex constraint

Suppose $X^i=[0,1]$ for $i=1,2,3$. $X=\prod_i X^i$ and $\mu_i$ is a measure on $B([0,1])$ and $\mu$ is the product measure. Let $f,g,h$ be $L^2(\mu)$ integrable functions satisfying $$0\leq ...
0
votes
1answer
32 views

Dirichlet series generating function of a sequence

To find the dirichlet series generating function of the following sequence $\left\{\sum_{n/d}d^q\right\}_{n=1}^\infty$ The series is like this $\frac{1^q}{1^s} + \frac{1^q+2^q}{2^s} + ...
1
vote
1answer
26 views

What is $n>1$ so that there is an $n\times n$ board with a perfect square number of squares?

There is an $n\times n$ board ($n>1$) such that the total number of different squares it contains is a square of an integer. For example, a $2\times 2$ board contains $5$ different squares. Find ...
3
votes
1answer
49 views

Permutations of cards with no adjacent pairs

We have a standard 52-card deck, and are looking at the possible shuffles/permutations of this deck. However, we have rubbed off the suits from the cards, so for every rank (aces, tens, etc.) all ...
0
votes
1answer
56 views

What is the algorithm to generate the cards in the game “Dobble” ( known as “Spot it” in the USA )?h

In the game Dobble ( known in the USA as "Spot it" ) , there is a pack of 55 playing cards, each with 8 different symbols on them. What is remarkable ( mathematically ) is that any two cards chosen at ...
5
votes
2answers
96 views

How many ways to select $k$ vertices of an $n$-gon?

I have a regular $n$-gon, of which I have to select $k$ vertices. The selections must be rotationally distinct; two selections would be considered equivalent if one is a rotation of the other. For ...
2
votes
2answers
43 views

the number of copy of 6-cycles in petersen graph

the number of copy of 6-cycles in petersen graph.I know that Petersen graph has ten copy of 6-cycles but I can't prove it.
1
vote
2answers
33 views

Arranging the word CLASSICS [on hold]

The letters of the word CLASSICS are to be arranged in a row. How many of the arrangements end with a letter other than S?
0
votes
1answer
14 views

Subdivide Unconditional Probability

Say, I have 6 urns, and balls of different color in each. I would like to compute the unconditional probability of drawing a red ball, when I somehow randomize over all urns. Now, my intuition tells ...
5
votes
1answer
110 views

Prove by combinatorial method that $ \frac{(2m)! \cdot (2n)!}{(m)! \cdot (n)! \cdot (m+n)!} $ is an integer [duplicate]

Prove that $$ \dfrac{(2m)! \cdot (2n)!}{(m)! \cdot (n)! \cdot (m+n)!} $$ is a positive integer, where $(m,n) \in \mathbb{Z^{+}}$ I have already solved it using Legendre's Formula ...
2
votes
3answers
52 views

Prove that every year contains at least $4$ months and at most $5$ months with $5$ Sundays

Prove that every year contains at least $4$ months and at most $5$ months with $5$ Sundays each. Miklos Bona rates this question as "less difficult than average" while I am stuck on it although I ...
0
votes
1answer
24 views

Number of subsets of $\{0,1,2,…,9\}$ with symmetric difference $\leq 2$

There is a problem asking to prove that among any 100 subsets of $\{0, 2, 3, \dots , 9\}$ there will be two with cardinality of their symmetric difference less than or equal to two. It is proven by ...
2
votes
0answers
26 views

Maximum independent sets of $k$-partite graphs

Consider a $k$-partite graph $G=(V,E)$. This means that its vertices can be partitioned into $k$ different independent sets, say $V_1,\dots, V_k$. Assume further that $|V_1|=\dots = |V_k|$. Under ...
0
votes
1answer
20 views

Solving a series in the proof of the expectation of the binomial distribution

I am studying the expectations and variances of the most common distributions. For the binomial distribution the mean is equal to $np$. Considering $p$ and $q$ independent variables and ...
2
votes
2answers
54 views

Nested sum $\sum_{i<j< \cdots < k} ij \cdots k$

I am wondering if there is any known closed form for the following nested sum? : $$ \sum_{i<j<\cdots <k} ij\cdots k $$ where each $i,j,\cdots,k =1, \cdots, n$ I tried the first one: $$ ...
0
votes
2answers
47 views

How many 2 digit even numbers can be formed from these numbers?

How many even 2 digit numbers can be formed from the numbers 3,4,5,6,7? The digits cannot repeat (you can't have 44 or 66 for example). I know the answer to this is 8, because I just wrote them all ...
1
vote
1answer
37 views

Proof Bell-Number $B(n+1)=\sum\limits_{i=0}^n\binom{n}{i}B(i)$

Let B(0) := 1 und B(n) for n$\geq$1 the counts of all sets partitions of [n]. The numbers B(n) are the Bell-numbers. For $n \geq 0$ prove that: \begin{equation} ...
-3
votes
0answers
37 views

Counting the number of ways. [on hold]

In how many ways can a person select $3m$ objects from a collection of '$2m$' distinct pens and '$(4m)$'identical pencils ? (order not important)
1
vote
1answer
33 views

Closed formula for ordinary power series generating function

To find the ordinary power series generating function of $\left\{\frac{1}{n+1}\right\}_2^\infty$, I tried to solve it like this, let $$\begin{align} f &= \frac{x^{n-2}}{n+1}, \text{ where }n \ge ...
1
vote
1answer
38 views

How many class schedules are possible?

You have $5$ choices of a math class, $2$ choices of history class, and $6$ choices of writing class. If you are planning to take one of each class, how many possible schedules could you have? What I ...
4
votes
2answers
46 views

Multiplication Principle and Inclusion-Exclusion: $2^n = \sum_{i = 0}^n (-1)^i \binom{n}{i} \binom{2n - 2i}{n - 2i}$

I began to compose an unnecessarily complicated answer to this question: If we had 25 people all who have 2 different balls, how would you work out how many combinations there would be if we want ...
4
votes
5answers
49 views

Counting clarification

In the text I am reading there's a question: From the digits $0, 1, 2, 3, 4, 5, 6$, how many four-digit numbers with distinct digits can be constructed? How many of these are even numbers? I get the ...
0
votes
0answers
39 views

A Good book for Combinatorial Theory

I am looking for a good book on Elementary Combinatorics (Olympiad level). For some reason I do not like Lint. I am currently reading "A Walk Through Combinatorics" by Miklos Bona and I find it really ...
1
vote
1answer
22 views

Incomplete beta integral

Let n be greater than one, and B be the beta integral, $$\sum _{j=0}^{\infty } C_j B_{\frac{1}{n}}(j+1,j+2)=\frac{1}{n}$$ Is it correct to call this an inversion formula? What possible ideas are ...
1
vote
2answers
42 views

how many ways to partition a set with k subsets, each of fixed size?

if $(v_1,...,v_k)$ is a partition of $n$, how many ways $M((v_1,...,v_k),n)$ is there to create a set (partition) of $k$ elements, each of size $v_i$ , i=1,...,k from $n \geq k$ distinct elements ? ...
-1
votes
1answer
50 views

prove $\sum \limits_{k=1}^n A(n,k){x+k-1 \choose n}=x^n$

A descent in the permutation $\sigma = a_1 \cdots a_n \in S_n$ is an index $i\in[n-1$] for which $a_i > a_{i+1}$. Let A(n, k) be the number of permutations of $[n]$ with $k-1$ descents where $n ...
3
votes
0answers
40 views

Is there an established notation for this “replacement” operation?

If $S$ is a set, define $$(x \to y) \cdot S := \begin{cases} (S \setminus \{x\}) \cup \{y\} & \text{ if } x \in S \text{ and } y \not \in S; \\ S & \text{ otherwise.} \end{cases}$$ In other ...