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)

-2
votes
0answers
27 views

Recall structures made from legos

Recall structures made from legos. We do not see these as just one lego brick after another, we see substructure. Try to find some substructure in the following lines of proof. Assume r is in Q. ...
1
vote
1answer
40 views

Number of elements in discrete $n$-dimensional simplex such that $x_1 \leq \ldots \leq x_n$

For positive integers $n,d$, how many elements are there in the set $S = \{(x_1,\ldots,x_n) \in \mathbb{Z}^n\ |\ 0 \leq x_1 \leq \ldots \leq x_n \wedge \sum_i x_i = d \}$? I'm hoping that the order ...
4
votes
1answer
15 views

Arrangement of any number of objects from $n$ objects

Prove that the total number of arrangements of objects by taking any number of objects from $n$ different objects is $\lfloor e \times n! - 1 \rfloor$, where $e$ is the natural base. I tried it ...
10
votes
4answers
1k views

N gunmen in a field

Let n be an odd integer. In some field, n gunmen are placed such that all pairwise distances between them are different. At a signal, every gunman takes out his gun and shoots the closest gunman. ...
-1
votes
1answer
54 views

Counting the maximum number of intersections.

Let $n$ be a positive integer. Points $A_1,A_2, \cdots, A_n$ lie on a circle. For $1 \le i <j \le n$, we construct $\overline{A_iA_j}$. Let $S$ denote the set of all such segments. Determine the ...
13
votes
3answers
405 views
+200

Finding real money on a strange weighing device

You have 50 coins which each weigh either 20 grams or 10 grams. Each is labelled from 0 to 49 so you can tell the coins apart. You have one weighing device as well. At the first turn you can put as ...
-2
votes
0answers
19 views

How many ways shuffle $n_1$ and $n_2$ balls when we but them together?

I have $n_1$ white balls and $n_2$ black balls, and I want to know how many ways I can make a distinct arrangement from them. For example , $n_1 = 2$, $n_2 = 1$ then there are three distinct ...
4
votes
2answers
68 views

Simplifying a combinatorial expression

Find \begin{eqnarray} \sum_{i=1}^{k-1}i(2k-2-i)\binom{2k}{2i+1} \end{eqnarray} I know how to find $\sum_{i=1}^{k-1}a_i\binom{2k}{2i+1}$ if $a_i$ is linear in $i$, but got stuck when $a_i$ is ...
0
votes
1answer
17 views

Counting weakly connected graphs with outdegree of exactly one.

If we count all graphs of $N$ labelled vertices, where each vertex has an outdegree of exactly $1$ with no self-loops allowed, we'll find that there are exactly $(N-1)^N$ of them (for every of $N$ ...
1
vote
1answer
30 views

Is this a binomial or multinomial question?

You can donate to a company: $10$ dollars , $20$ dollars or nothing. In a mall there are $70$% young people and $30$ % old people. $50$% from the old people aren't donating anything. ...
0
votes
1answer
19 views

How many n-permutations have no substrings of the type (j,j+1)?

How many n-permutations have no substrings of the type $(j,j+1)$? $$1\leq j\leq n-1 \text{ and } n\geq 2$$ For example, let n be 5: [3 2 1 5 4] is one of the permutations we have to count. [4 ...
6
votes
1answer
3k views

The number of partitions of $n$ into distinct parts equals the number of partitions of $n$ into odd parts

This seems to be a common result. I've been trying to follow the bijective proof of it, which can be found easily online, but the explanations go over my head. It would be wonderful if you could give ...
2
votes
2answers
37 views

Erin rolls 4 four-sided dice all at once, then can roll a subset of her choosing a 2nd time. What is the probability of getting all the same number?

Here's what I have so far: All 4 same on first try = (1/4)^4 * 4 3 same, then get 4th on 2nd roll = 4 * (1/4)^3 * (3/4) * (4!/3!) Here's where I'm confused: 2 same = 4 * (1/4)^2 * (3/4)(2/4 :to ...
2
votes
1answer
41 views

How do I calculate these sum-of-sum expressions in terms of the generalized harmonic number?

I know that $$\sum_{m=2}^k\sum_{n=1}^{m-1}(nm)^{-s}=\frac 12((H_k^s)^2-H_k^{(2s)})$$ and $H_k^s=\sum_{n=1}^kn^{-s}$ But, how would I go about finding identities in terms of the harmonic number like ...
1
vote
4answers
119 views

Binomial Sum: Values

I need this as lemma. Regard the sums: $$S_k:=\sum_{n=0}^N\binom{N}{n}(-1)^{N-n}n^k\quad(k\in\mathbb{N}_0)$$ Then it holds: $$S_k\stackrel{k<N}{=}0\quad S_k\stackrel{k=N}{=}N!$$ How can I check ...
0
votes
1answer
181 views

King and Devil problem

On a unlimited two-dimensional plane, the plane is separated into two-dimensional grid point by line $x=k$, $x=-k$, $y=k$, $y=-k$ ($k$ is integer). There is a game like this : A king could move to any ...
2
votes
3answers
1k views

Bell numbers (number of partitions of set of cardinality n) recurrence relation proof

Let $X$ be a set of cardinality $n$. How many partitions does it have? The users on the website found that these are the so called bell numbers. hey also pointed out the following recurrence relation: ...
0
votes
1answer
28 views

Numbers of factors of (n)(n+1)/2 is product of exponents?

I was trying to find the number of factors of $n(n+1)/2$, and I read this blog article, and it says that the number of factors of it is the product of its prime factor's exponents with one added to ...
1
vote
0answers
31 views

How to Evaluate this Summation to Find a Closed Form

While taking the incomplete Bell Polynomil of $x^a$ i found out that: $$ B_{n,k}^{x^a}(x) = x^{ak-n} \sum_{m=0}^k \frac{(am)!(-1)^{k-m}}{m!(k-m)!(am-n)!} $$ Now, what i am wondering is, what is the ...
3
votes
4answers
86 views

Why count it this way?

This is a very very elementary problem solving technique I was taught some time back. I have been using it but now looking at it, I find it kinda strange why it should be this way. Typically, the ...
2
votes
1answer
38 views

Distribution of K balls in N Cells with limitations

In how many ways can i distribute $k$ balls in $n$ numbered cells with the following limitations: 1.Each cell has different number of balls in it 2.Given each cell has more balls than the cell ...
0
votes
0answers
37 views

Stirling transform of $(k-1)!$

While reading about combinatorial mathematics, I found this article about the Stirling transform which caught my attention. So, if I wanted to find the Stirling transform of, for instance, $(k-1)!$, ...
2
votes
3answers
35 views

Probability theory combinatoric problem

A total of $n$ bar magnets are placed end to end in a line with random independent orientations. Adjacent ends with equal polarities repel each other, and adjacent ends with opposite polarities ...
0
votes
0answers
35 views

Prove the function is nondecreasing

Lets take: $A_1,...,A_n$ family of finite, nonempty sets. Define: $$f(t)=\sum_{k=1}^n\left( \sum_{1\le i_1<...<i_k\le n}(-1)^{k-1}t^{|A_{i_1} \cup ... \cup A_{i_k}|} \right)$$ for $t \in [0,1]$. ...
0
votes
3answers
31 views

Combinations and Double Factorials

In a village, there are 10 boys and 10 girls. The village matchmaker arranges all the marriages. In how many ways can she pair off the 20 children, if homosexual marriages (male-male or female-female) ...
2
votes
1answer
26 views

Combinatorics strategie for order

At the moment I have to deal a bit with Combinatorics but I have some problems with it. Let's say I have following situation: Spend 1500 Euro to 4 people so that everyone has a multiple of 100 ...
1
vote
2answers
87 views

How to prove even subsets equal to odd subsets? [duplicate]

There is question that I don't know how to prove. we have set $A=\{1,2,3,\ldots,n\},\; O=\{B\mid B⊆A,\text{ odd }B\},\; E=\{B\mid B⊆A,\text{ even }B\}$ it ask to prove that subsets even equal to ...
4
votes
3answers
69 views

Number of subsets with even number of elements [duplicate]

Let $|X|=n$. How to find all number of subsets $X$ consisting of an even number of elements?
1
vote
2answers
31 views

Arrangements in which only two of the three empty chairs are next to each other

While studying, I got stuck on this problem: "Seven identical chairs in a row are to be seated by four students. How many arrangements are there such that the only two of the three empty chairs are ...
0
votes
3answers
52 views

Proof for number of completely odd and even subsets.

While studying, I read this: "A subset of integers $1,2,...,n$ has the property that the sum of its members is odd. The number of such subsets is $2^{n-1}$." I also read this: "A subset of integers ...
2
votes
1answer
447 views

Counting distinct restricted integer partitions of $n$ into exactly $k$ distinct parts less or equal then $M$

How can I find the number of partitions of $n$ into exactly $k$ distinct parts, where each part is at most $M$? The number of partitions $p_k(\leq M,n)$ of $n$ into at most $k$ parts, each of size at ...
0
votes
0answers
32 views
+50

Mixing up seating charts: Measuring “mixedness” over time

Background: My class has $10$ students and $3$ tables; naturally, the students are distributed with $3, 3,$ and $4$ seated at the individual tables. On the second day of class, students sat in the ...
3
votes
1answer
44 views

An inequality relating to moves to P-positions in Nim

I have been researching this variant of Nim. I have been unable to prove the following claim. What is annoying is that I feel I am missing something really obvious. Does anyone have any ideas on how ...
0
votes
1answer
21 views

Counting functions and stirling numbers

Let S= { f | f: A $\rightarrow$ B, |Image(f)|=k}. |A|=m, |B|=n. where k $ \le n, k \le m $ |S|=$ {n \choose k} $ S(m,k) k!. where S(m,k) are the striling numbers of the second kind. What I can't ...
-1
votes
1answer
43 views

Calculating distance between two squares of a board

Given an $n\times n$ board, for example a chess board 8x8, with the squares ordered in a Little-Endian Rank-File Mapping. Is there a direct way to calculate the distance between two squares using ...
7
votes
4answers
12k views

A fair 6 sided dice is rolled 4 times. What is the probability that at least 3 of the numbers will be either 1 or 6?

I'd really love a sanity check here as I walk through what I believe is the solution. Total possible outcomes = $6^4 = 1296$ Possible combinations of 3 rolls being either 1 or 6 = $({}_4C_3)\cdot2 = ...
1
vote
1answer
26 views

Generating Finite Groups By Random Premultiplication With Generators

Let $G$ be a finite group with identity $e$ and $S$ be a set which generates $G$. Is it always possible to define a procedure of the form: Start with $x=e$. With probability $p_1$, replace $x$ with ...
13
votes
6answers
271 views

Binomial Sum Related to Fibonacci: $\sum\binom{n-i}j\binom{n-j}i=F_{2n+1}$

How would I prove $$ \sum\limits_{\vphantom{\large A}i\,,\,j\ \geq\ 0}{n-i \choose j} {n-j \choose i} =F_{2n+1} $$ where $n$ is a nonnegative integer and $\{F_n\}_{n\ge 0}$ is a sequence of ...
1
vote
4answers
47 views

Proof for number of ways to select k non-consecutive elements from n consecutive terms. [duplicate]

While studying, I found a formula that found the number of ways to select k non-consecutive elements from n consecutive terms, not necessarily the first n consecutive terms, but any n consecutive ...
1
vote
1answer
42 views

What is the sum of all $k$ values?

In an urn there are a certain number (at least two) of black marbles and a certain number of white marbles. Steven blindfolds himself and chooses two marbles from the urn at random. Suppose the ...
1
vote
1answer
42 views

How to manipulate the bound on the summation

$$ B_n^{f^2}(x) = \sum_{k=1}^n\sum_{j=0}^{n-k} 2^{k-j} {j+k \choose j} \frac{d^j}{df^j}[f^k] B_{n,j+k}^f(x) $$ I am looking to have the bounds switched, can someone show me exactly how this is done? ...
1
vote
0answers
15 views

Available lists of all latin squares up to order 5?

There are available online lists of the number of all latin squares up to order 11, e.g.: https://oeis.org/A002860. For a permutation-based test of a latin square design, one option is to fit the ...
4
votes
0answers
26 views

Proving that the intersection of two closed sets is closed in a matroid

I am stuck on a little homework problem I have. Here, $M$ is a matroid with rank function $R$. I am given this definition: In a matroid $M$, a set $A$ is closed if $R(A \cup e) > R(A)$ for all $e ...
4
votes
2answers
81 views

No Adjacency Combinatorics Problem via Generating Function

I would like to find the generating function solution for the following combinatorics/probability problem. I have a combinatorial solution and the generating function deduced thereof. But I can not ...
6
votes
2answers
59 views

$\sum_{k=1}^n \binom{n}{a_1,a_2, \cdots , a_k} \binom mk \binom{k}{b_1,b_2, \cdots , b_l}= m^n,$

(Own) Let $n,m$ be positive integers such that $m>n$. Prove that $$\sum_{k=1}^n \sum_{a_1+a_2 + \cdots +a_k=n} \binom{n}{a_1,a_2, \cdots , a_k} \binom mk \binom{k}{b_1,b_2, \cdots , b_l}= m^n,$$ ...
2
votes
1answer
25 views

Tuples in cartesian product without duplicates

I have $n$ sets $S_1,\ldots,S_n$ and I would like to count the number of tuples $(i_1,\ldots,i_n)\in S_1\times\cdots\times S_n$ such as $i_h\neq i_k$ $\forall h,k\in \{1,\ldots, n\}$. Is there a ...
2
votes
0answers
43 views

Unique ways to distribute k1, k2, .. colored balls into n boxes uniquely

Example: Uniquely distribute 2 Red Balls and 4 Blue Balls into 3 boxes: [B][BB][RRB] [B][BBB][RR] [B][R][RBBB] [B][RB][RBB] [BB][R][RBB] [BBB][R][RB] Answer: ...
1
vote
1answer
49 views

Name of the numbers defined by $T(p,q) = T(p-1,q) + T(p,q-1)$?

I came across these numbers : $$ T(p,q)= \sum_{k=0}^{q-1} {p+k-1 \choose p-1} + \sum_{l=0}^{p-1} {q+l-1 \choose q-1} \quad p,q \in \mathbb{N} $$ While trying to solve this recurrence relation : $$ ...
6
votes
1answer
231 views

Special Products of Transpositions

[Edit. Significantly expanded to add examples and (I hope) clarification. Feel free to skim by reading the gray boxes.] A colleague asked me for insights on a collection of special permutations, ...
4
votes
1answer
92 views

A Combinatorial Sum!

Is there a closed form formula for the following sum \begin{equation} F(x;n,m)=\sum_{k=0}^{\min\{n,m\}} {n \choose k}{m \choose k}k!\ x^{k}=n! \, m!\sum_{k=0}^{\min\{n,m\}}\frac{1}{k!(n-k)!(m-k)!} ...