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
140 views

Generating functions for partitions of n with an even number of parts and odd number of parts, and their difference.

I've been trying to figure this out for more than 10 hours. So far I have, for even number of partitions, $$P_e(x)=\sum_{k\ge1}(x^{2k}\prod_{i=1}^{2k}\frac{1}{1-x^i})$$ and for odd numbers ...
1
vote
0answers
13 views

Bound on difference of two i.i.d. variables [duplicate]

Prove that for every two independent, identically distributed real random varaibles $X,Y$, $$Pr(|X-Y|\leq 2)\leq 3\cdot Pr(|X-Y|\leq 1)$$ [Source: The probabilistic method, Alon and Spencer]
1
vote
0answers
68 views

Maximizing Stirling numbers of the second kind

In Stanley's Enumerative Combinatorics, there is a question on Chapter $1$ which goes as follows: Let $S(n,k)$ denote a Stirling number of the kind (ie, $S(n,k)$ is the number of ways to to ...
0
votes
1answer
30 views

Distributing Apples and oranges. confused about solution

How many ways are there to distribute 4 identical oranges and 6 distinct apples into 5 distinct boxes I know you find number of ways for apples which is 5^6. The solution tells me that the ways for ...
0
votes
1answer
59 views

number of pairs of integers whose sum is even

Given the set of integers from 1 to 9, how many combinations sum to an even number? I got 511. Here's my approach: I first consider 3 sets: $X$: the non empty set of all even numbers: ...
1
vote
0answers
29 views

Approximate Solution to Backwards Recurrence of Dynamic Game

Suppose we keep tossing a fair dice until we reach some cumulative sum greater than or equal to $N$. Then, let $S_k$ be the expected value of the final sum, given that the current sum is $k$. We have ...
2
votes
1answer
103 views

Expected number of returns to zero in a symmetric random walk - closed form

The expected number of returns of a symmetric random walk is given by $\sum_{k=0}^n \binom{2k}{k} / 2^{2k} -1$ The exercise is to compute an explicit form for this. I tried to do this in the ...
3
votes
2answers
147 views

Probability that each bucket has $\geq 3$ balls

There are $30$ buckets. John throws $20$ balls, each time landing uniformly among the buckets. What is the probability that no bucket contains $\geq 3$ balls? If the question were $\geq 2$ balls, we ...
1
vote
1answer
70 views

Beautiful logical combinatorics problem

TV series were aired for 5 years. Every day at most 2 episodes were shown. Every year, starting from the second one, either 40% more, or 40% less episodes, than the previous year, were aired. The ...
0
votes
1answer
32 views

Question in permutations

When we use this law? And in any case we use it? Thank you and I wish clarification.
1
vote
1answer
44 views

Beautiful problem about 11 statements

11 pieces of paper are on a line. On each of them one of 11 statements is written (all are different on each paper): 1)No false pieces of paper to the left 2)Exactly 1 false paper to the left ...
0
votes
1answer
28 views

Filling and painting bowls

I only know basic things about combinatorics, but I encountered a problem. You have 60 bowls. Then you do the following: Fill 30 bowls with one ball Fill 20 bowls with two balls Fill 10 bowls with ...
2
votes
1answer
91 views

Finding number of ways to get a sum of $100$

If we are given to find the number of ways 10 positive integers can sum to 50, we simply find the coefficient of $x^{100}$ in $(x+x^2+...+x^{90})^{10}$, which turns out to be $\binom{99}{90}$. But ...
1
vote
1answer
51 views

Mix of permutation and combination

a car can hold 3 people in the front seat and 4 in the back seat. In how many ways can 7 people be seated in the car if John and Samantha must sit in the back seat and there is only one driver? the ...
1
vote
2answers
217 views

Combinatorics question. Probability of poker hand with one pair

If we assume that all poker hands are equally likely, what is the probability of getting 1 pair? So the solution is I understand nominator part, but I do not understand why in denominator we have ...
1
vote
1answer
35 views

Proving the binomial coefficients by induction (half-done, but need help)

Defining the binomial coefficients $n \choose k$ as follows, i) for all $n \in \mathbb{N}$, $\binom{n}{0} = \binom{n}{ n} = 1$ (ii) for all $2 \leq n \in \mathbb{N}$ and for all $ 1 \leq k \leq n-1, ...
0
votes
1answer
15 views

Number of Distinct Elements in Set of Products of 2 Matrices

Let $X=\begin{pmatrix}\cos\frac{2\pi}{5} & -\sin\frac{2\pi}{5}\\\sin\frac{2\pi}{5} & \cos\frac{2\pi}{5}\end{pmatrix}$ and $Y=\begin{pmatrix}1 & 0\\0 & -1\end{pmatrix}$. Find the ...
1
vote
1answer
105 views

Counting and probability gift exchange problem

There are 50 people (numbered 1 to 50) and 50 identically wrapped presents around a table at a party. Each present contains an integer dollar amount from $1 to $50, and no two presents contain the ...
0
votes
2answers
111 views

Number of Ways to Break a Chocolate Bar

In how many ways can you break a off a rectangular piece of chocolate from a chocolate bar with m x n squares. [We must respect the structure of the chocolate bar, that is break only along horizontal ...
2
votes
2answers
36 views

Probability, why is this wrong? (Combinations and Permuations)

Why is this the wrong approach to solve this problem? "There are 65 students. 20 of them are sophomores, 20 are freshmen, 15 are juniors and 10 are seniors. When picking a 4 student committee, ...
1
vote
1answer
32 views

Ways in which 2k indices can be assigned so that every index is equal to at least one other

In trying to approximate a certain power of a sum, I wound up with this issue: There are 2k indices, $i_1, i_2, ..., i_{2k}$, each of which can take on any of the values {$1, 2, ..., n$}. I need to ...
-1
votes
2answers
49 views

Number of Pairs of Subsets

Find the number of Pairs(A,B) of subsets of[n] such that A ⊆ B? I just need clarification in my thought process. My professor's wording at times can through me off. I just want to know if i am on the ...
5
votes
1answer
96 views

Show that $n!^{n+1}$ divides $(n^2)!$

My attempt so far is by induction. Let $f(n) = \frac{(n^2)!}{n!^{n+1}}$, I will try showing that $f(n)$ is a positive integer for all $n$. We have $f(0) = \frac{0!}{0!^{n+1}} = 1$. Now assume for ...
3
votes
3answers
55 views

Probability 4 different numbers $ a, b, c , d$ are solution of $a+b=c+d$

Let $N=\{1,\ldots,n\}$ We choose $a$, $b$, $c$, $d$ - different random numbers from $N$. What is probability of $a+b=c+d$?
1
vote
1answer
65 views

Showing that the number of ways to cut a 200 x 3 board into 1 x 2 dominoes is divisible by 3.

Showing that the number of ways to cut a 200 x 3 board into 1 x 2 dominoes is divisible by 3. My only idea is to assume the opposite, make some needed arrangement, and to show that changing the ...
1
vote
1answer
27 views

N Boxes and M babies question.

There are N boxes placed in a straight line. Adjacent boxes are separated by 1 unit. The Babies which are a total of M in number decide to play in this arena of boxes by moving from one box to ...
1
vote
2answers
98 views

Selecting books on a shelf so that there are at least 3 unselected between any two selected books

How many ways are there to select $k$ out of $n$ books on a shelf so that there are always at least $3$ unselected books between selected books? (Assume $n$ is large enough for this to be possible.) ...
1
vote
1answer
41 views

distributing r distinct objects into n-distinct boxes when repetition is allowed

Suppose there are 5 students and we are trying to create 3 distinct commissions which every student must be in at least one commission and every commission must have at least 2 members. what is the ...
0
votes
1answer
30 views

combination tricky question

A sports team consists of $5$ bowlers (or pitchers), $9$ batsman and $2$ keepers (or back-stops). How many different teams of $11$ players can be chosen from the above squad if the team consists of ...
1
vote
2answers
81 views

Two hundred balls into one hundred boxes

We have distributed two hundred balls into one hundred boxes with the restrictions that no box got more than one hundred balls, and each box got at least one. Prove that it is possible to find some ...
2
votes
1answer
42 views

Help in finding $\lim_{n\to \infty}\left ( \sum_{k=1}^{n} \frac{1}{\binom{n}{k} } \right )^n$.

I am not able to get a solution for this problem . Of finding the limit $$\lim_{n\to \infty}\left ( \sum_{k=1}^{n} \frac{1}{\binom{n}{k} } \right )^n$$ I have tried using Mathematica and that ...
0
votes
2answers
67 views

What is the number of nonnegative solutions of a linear equation?

What is the number of solutions of a linear equation? for example look at this equation: $X_1+X_2+...+X_n=r$ The number of solutions is the following formula, because the way of choosing $r$ objects ...
1
vote
0answers
26 views

A question involving Partial Steiner Triple Systems

I've been given the following question, which I think I've completed, but I just wanted to check whether what I've said is valid. Suppose that a PSTS(23) with a $K_5$ leave is constructed using ...
0
votes
1answer
44 views

Element matrix multiplication representation

Matrix element by element multiplication defined : $C=A*B$ $c_{ij}=a_{ij}b_{ij}$ Is this multiplication can be represented with stardant matrix multiplication or Kronecker product ?
0
votes
1answer
46 views

Positive Integer Solutions to an Equation with Individual Variable Constraints

Find the number of positive integer solutions to $ x_1 + x_2 + x_3 + x_4 + x_5 = 100 $ if $x_1 \le 30$, $x_2\le40$, $x_3\le50$, $x_4\le60$, and $x_5\le70$.
1
vote
3answers
37 views

What is the formula for the sum of $^{n}C_{k}$ for fixed $k$ and varying $n$?

I am searching for a formula of sum of binomial coefficients $^{n}C_{k}$ where $k$ is fixed but $n$ varies in a given range? Does any such formula exist?
0
votes
1answer
60 views

The existence of two couples of dancers that did not exchange partners

At a homecoming dance, no boy dances with every girl, but each girl dances with at least one boy. Prove that there are two couples, gb and g'b', who dance, such that g doesn't dance with b' and g' ...
0
votes
1answer
20 views

Evaluating the $L_2[-1, 1]$ inner product on rescaled Legendre polynomials

Let $z_n(t) = \sqrt{\frac{2n+1}{2}} \frac{1}{2^n n!} \frac {d^n}{dt^n} (t^2-1)^n$, a rescaled Legendre polynomial. As an intermediate step of a larger problem, I need to show that in terms of the ...
0
votes
3answers
76 views

Combinatorial - how many ways to divide objects into two groups

As a part of a bigger problem I have to determine In how many ways $37$ different objects can be divided among two groups of $32$ and $5$ objects each if i) object $A$ and $B$ cannot belong to the ...
5
votes
1answer
59 views

Bound on number of breakable sets

Let $\mathcal{S}$ be a finite family of finite sets. A finite set $A$ is called breakable if for every $B\subseteq A$, there exists $S\in \mathcal{S}$ such that $A\cap S=B$. Show that at least ...
-1
votes
1answer
89 views

how many people are at the party

At a party, each person shakes hands with 5 other people. There are a total of 60 handshakes. How many people are at the party? i am lost because of the 60 hand shake that is mentioned.
1
vote
3answers
183 views

Show that a set of vectors is linearly dependent

Show that the set $S = \{(3, 2), (−1, 1), (4, 0)\}$ is linearly dependent by finding a nontrivial linear combination of vectors in the set whose sum is the zero vector. (Use $s_1$, $s_2$, and ...
0
votes
1answer
23 views

Distributing different things into groups

How to distribute four different things in two groups.. Actual question was you have four different types of animals a wolf, a monkey, a tiger and a lion and you have two cages. Find No. Of ways of ...
0
votes
1answer
39 views

How many distinct partials of order $k$ for a function $f: \mathbb{R}^{n}\rightarrow\mathbb{R}$?

Studying for the math subject GRE, and I come across the titular question. I didn't take any combinatorics or probability courses in college, and I'm realizing I have no intuition for counting. Could ...
1
vote
0answers
48 views

Counting similar pairs

I was given a simple programming assignment: Your task is to quickly find the number of pairs of sentences that are at the word-level edit distance at most 1. Two sentences S1 and S2 they are ...
0
votes
1answer
45 views

permutations combinations

Q1. Total number of permutations of k diferent things , in a row , taken not more than r at a time(each thing may be repeated any no. of times) is equal to Q2. A teacher takes 3 children from her ...
0
votes
1answer
61 views

combinatorics- persons in group

Let $$ n = \binom {k + b-2}{k-1} \text{ and }k, b\ge 2 $$ Prove that in each group of at least n persons there is k person is familiar with everybody or there are b persons two did not know each ...
0
votes
4answers
59 views

Simplifying a fraction with binomial coefficients [closed]

I'm trying to do a simple combination but seem to forget the shortcut. It is $${\binom{6}{2}+\binom{4}{2} \over \binom{10}{2}}$$ Now finding the answer on my calculator is easy, the problem is that I ...
1
vote
0answers
13 views

How to generate list of values that sum to X given n spots where each value is unique.

For example: Given 2 spots and sum 3 the list would be {1,2} Given 2 spots and sum 4 list would be {1,3} does not contain 2 as putting 2 in both spots violates the uniqueness of each value.
9
votes
1answer
220 views

Toss a fair die until the cumulative sum is a perfect square-Expected Value

Suppose we keep tossing a fair dice until we want to stop, at which point the game ends and our score is the cumulative sum, or until the cumulative sum is a perfect square, in which case we lose and ...