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
2answers
171 views

When adding zero really counts …

Note: Although adding zero has usually no effect, there is sometimes a situation where it is the essence of a calculation which drives the development into a surprisingly fruitful direction. Here is ...
1
vote
1answer
73 views

Parity of $\sum_{i=1}^{n}\lfloor \log_2(i) \rfloor$

Let, $L=\sum_{i=1}^{n}\lfloor \log_2(i) \rfloor $. Problem: Find $n$ for which $L$ is odd. In other words, find a closed form expression (function) $f(n)$of variable $n$ such that $L$ is odd/even if ...
3
votes
2answers
45 views

Help me understanding what actually i counted with inclusion-exclusion

I tried to solve following task: Count number of $8$-permutations from $2$ letters $A$, $2$ letters $B$, $2$ letters $C$ and $2$ letters $D$ where exactly one pair of same letters are adjacent in ...
0
votes
0answers
30 views

Transforming generating functions into algorithms that generate combinatorial objects

I've stumbled upon this paper where they write about random sampling of combinatorial objects. For sampling to be proper one has to know some core numbers (probabilities). However, I'm not interested ...
1
vote
1answer
62 views

Need to prove that there is a continuous sequence which contains 100 cup of coffee , i.e. a man drinks one cup of coffee at the day.

A man can drink at least one cup of coffee at the day. After one year he drinks 500 cup of coffee. Need to prove that there is a continuous sequence which contains 100 cup of coffee, i.e. a man drinks ...
4
votes
1answer
35 views

When is a recurrence the sum of the powers of the roots of a polynomial?

Newton's formula allows one to calculate the sum $S_n(P)$ of the $n$th powers of the roots of a given monic polynomial $P$ without finding the roots explicitly. (This works even when the roots ...
0
votes
6answers
37 views

Arrangement of 12 boys and 2 girls in a row.

12 boys and 2 girls in a row are to be seated in such a way that at least 3 boys are present between the 2 girls. My result: Total number of arrangements = 14! P1 = number of ways girls can sit ...
3
votes
2answers
72 views

Rewriting product to a binomial

I'm currently researching Wigner matrices. I wanted to calculate the moments of its spectral density. The probability density is $$\frac{1}{2\pi} \sqrt{4-x^2} \text{ for } x \in [-2,2] $$ I have ...
-1
votes
1answer
48 views

Method of integration [duplicate]

We have to find the integration of the following function I tried but got stuck can anybody help me how to proceed . Is there anyother method to solve this
0
votes
1answer
58 views

Isi B.Math Fibonacci problem.

Let $\dbinom{n}{k}$ denote the binomial coefficient $\frac{n!}{k!(n-k)!}$ , and $F_m$ be the $m^{th}$ Fibonacci number given by $F_1=F_2=1$ and $F_{m+2}=F_m+F_{m+1}$ for all $m\geq 1$. Show that $\...
0
votes
2answers
43 views

How to correctly count the probability for a computer game situation? [closed]

Imagine we have the following situation in a computer game: One player has two minions with 30 and 6 hitpoints correspondingly. Another player casts a spell which does 12 times 1 damage (for each of ...
5
votes
1answer
651 views

Calculating the Shapley value in a weighted voting game.

Given a special case of WVG (Weighted Voting Game) of $a$ 1s and $b$ 2s and a quota q, $ [q:1,1,1,1..1,2,2,..2] $. I need help with calculating the Shapley value of a player with a weight of $2$ and a ...
3
votes
1answer
53 views

Each $2\times 5$ rectangle contains $1\times 3$ rectangle

A $60\times 60$ board is partitioned into rectangles of size $2\times 5$ (or $5\times 2$). Is it true that there always exist another partition into rectangles of size $1\times 3$ (or $3\times 1$) ...
2
votes
0answers
31 views

Number of zigzag permutations of first $n$ natural numbers given start and end value

Given $n$ and $1\le s,e\le n$, how to compute the number of zigzag permutations of first $n$ positive integers starting with $s$ and ending with $e$? I tried formulating a recurrence relation but can'...
1
vote
0answers
96 views

Joint probability with constraint [closed]

Let's say that one is conducting an experiment with 8 units and 4 units have to be assigned to treatment. Assuming all units' respective treatment assignment probabilities are greater than 0 and less ...
8
votes
0answers
95 views

How many ways can I arrange the numbers $1$ to $N$ with this divisibility condition?

For the numbers $1, \ldots, N$, how many ways can I arrange them such that either: The number at $i$ is evenly divisible by $i$, or $i$ is evenly divisible by the number at $i$. Example: for N = 2$...
1
vote
0answers
44 views

Given N blocks, find the number of unique shapes in a NxN block

Constraints: The blocks must be adjacent to each other. i.e. A pair of blocks must have a common edge or vertex. Any shapes that are formed by flipping or rotating or mirroring should be considered to ...
1
vote
3answers
155 views

Find general solution for the equation $1 + 2 + \cdots + (n − 1) = (n + 1) + (n + 2) + \cdots + (n + r) $

A positive integer $n$ is called a balancing number if $$1 + 2 + \cdots + (n − 1) = (n + 1) + (n + 2) + \cdots + (n + r) \tag{1}$$ for some positive integer $r$. Problem: Find the general ...
0
votes
0answers
26 views

Distribution for playing n scratcher lottery tickets

If I know the prize distribution for a scratcher lottery ticket (i.e. the various prize amounts and the probability associated with each prize) is there a way to form a distribution for playing, say, ...
2
votes
1answer
33 views

Binomial identity for bijection $\mathbb N\times\mathbb N\to\mathbb N$

In a book I'm currently reading it is said (without proof) that, for an enumeration $d$ of $\mathbb N\times\mathbb N$ defined by $$d(0)=(0,0),\ d(1)=(0,1),\ d(2)=(1,0),\ d(3)=(0,2),\ d(4)=(1,1),\ d(5)=...
2
votes
1answer
23 views

double summation of conditional variable depending on sum of integer

I am having trouble with taking a certain summation and finding an explicit value for the summation. The summation is: $$ S = \sum_{w=3}^a \lambda_w \sum_{m=w}^a \lambda_m $$ The only information ...
1
vote
1answer
48 views

Algorithm for calculating multiset permutations

I have this algorithm to calculate multiset combinations: $$\mathcal P(k; m_1, m_2, \ldots, m_n) = \Sigma \binom{c(i_1)}{\lambda_1}\ \binom{c(i_2)-\lambda_1}{\lambda_2} \cdots \binom{c(i_s)-\lambda_1-...
2
votes
1answer
56 views

Is there a more concise expression of this product?

In a longer computation, I have stumbled upon the following product, where $k,r \in \mathbb{N}_0$ are fixed numbers: $$\prod_{0 < i_0<i_1<\dots<i_r\leq k} (i_r-i_{r-1})(i_{r-1}-i_{r-2})\...
2
votes
3answers
94 views

Combinatorics on the word Abracadabra

How many different 'words' can be created using all the characters of 'ABRACADABRA'? In how many of the 'words' that there are no identical characters one next to the other? So, For the first part, ...
2
votes
3answers
58 views

Doubt in finding number of integral solutions

Problem : writing $5$ as a sum of at least $2$ positive integers. Approach : I am trying to find the coefficient of $x^5$ in the expansion of $(x+x^2+x^3\cdots)^2\cdot(1+x+x^2+x^3+\cdots)^3$ . ...
0
votes
4answers
67 views

In how many ways can a group of $n$ people composed of six types be created with restrictions?

Suppose we need to create a group of $n \geq 20$ people with the following types and requirements: Scientists, at least 2; Pro Athletes, at least 1; Mathematicians, at least 5; Plumbers, at least 0; ...
0
votes
0answers
14 views

Noetherian Rings Definition, countability?

In my book (Jantzen, Algebra, 2014), Noetherian rings are defined by three equivalent conditions. I wonder how the first two can be equivalent: Every ascending chain of ideals $(a_1) \subset (a_2) \...
2
votes
4answers
70 views

Algebraic expression of Prime of form $4k-1$

Every prime of the form $4k+1$ can be written as an algebraic expresion of sum of two squares. Question: If $p=4k-1 $, can it be written as a sum of some powers? (algebraic exprssion like $p= y^3+ (...
2
votes
2answers
48 views

Using the Binomial Identity, prove that ${n\choose k}+2{n\choose k+1}+{n\choose k+2}={n+2\choose k+2}$

Using the Binomial Identity, prove that: $${n\choose k}+2{n\choose k+1}+{n\choose k+2}={n+2\choose k+2}$$Because this is in the form of a Binomial Coefficient, I can break down the LHS further:$$\left(...
1
vote
2answers
35 views

Half from any $2n$ but not $2n+2$

Let $n$ be a positive integer. What is the length of the longest possible sequence of $0$'s and $1$'s such that among any $2n$ consecutive numbers, exactly half are $0$'s, but among any $2n+2$ ...
1
vote
3answers
41 views

Expected Value for Heads for Unknown Weighted Coin Given Head First Flip

This is a combinatorics problem, and I think it involves expected values and conditional probability, but I don't know how to use them: "A bag contains an infinite number of coins whose probabilities ...
1
vote
2answers
554 views

Number of binary search trees on $n$ nodes of height up to $h$

How can I find the number of binary search trees up to a given height $h$, not including BSTs with height greater than $h$ for a given set of unique numbers $\{1, 2, 3, \ldots, n\}$? For example, if ...
2
votes
0answers
18 views

Finitely many steps to $n$-stone pile.

I have a combinatoric problem still unsolved: $2n$ ($n$ is a positive integer) stones are divided into $3$ piles. In each step, we pick half of a pile which has even number of stones and move those ...
1
vote
0answers
111 views

The number of lattice points in d-dimensional ball

The following paper states that the number of lattice points in a $d$-dimensional ball of radius $R$ is $V_d R^d + O(R^\alpha)$ where $\alpha = d - 2$ and $V_d$ is the volume of the unit $d$-...
1
vote
1answer
76 views

Generating function for lattice points in a sphere

This is a note in Sedgewick's Analytic Combinatorics: The number of lattice points with integer coordinates that belong to the closed ball of radius n in d-dimensional Euclidean space is $\...
2
votes
1answer
440 views

number of lattice points in an n-ball

I have faced a problem in my work and I will appreciate any hint/reference as I am not much into the lattice problems. Assume an n-dimensional lattice $\Lambda_n$ with generator matrix $G$. Note that ...
5
votes
2answers
444 views

Counting Lattice Points with Ehrhart Polynomials

Let $\bar{\mathcal{P}}$ denote the closed, convex polytope with vertices at the origin and the positive rational points $(b_{1}, \dots, 0), \dots, (0, \dots, b_{n})$. Define the Ehrhart quasi-...
0
votes
2answers
441 views

Counting lattice points interior to a polygon

If I define an integer lattice $\Lambda \subseteq \mathbb{Z}^2$ with a basis given by $$\omega_{1} = a \hat{i} + b\hat{j}, \;\;\; \omega_{2} = -b \hat{i} + a\hat{j}$$ How can I count how many lattice ...
2
votes
2answers
48 views

Find least number of radial-subgraph of a graph

Background: Here is a group G of a people, one maybe another's friend. How to select least number of people to be a leader of a subgroup, so that everyone in the group G has a friend as a leader? ...
0
votes
2answers
57 views

In AB + BC + AC = N, how can I find all possibilities for A, B and C in less than n³ computational time?

The problem is the one on the title. Given a N, find all possibilies for A, B and C that make this true: $AB+BC+AC = N$when $A \ge B \ge C$. This code in C do the job: ...
1
vote
4answers
52 views

Bayesian probability problem?

Problem: In a city there are three types of taxis which drive towards the airport. 30% are blue, 20% green, 50% yellow. They take there customers too late with probabilities 0.1,0.2,0.3 respectively. ...
0
votes
3answers
36 views

Prove that if a collection of subsets of {1,..,n} that each pair of subsets has at least one element in common, there are at most $2^{n-1}$ subsets

Full question: Prove that if a collection of subsets of {1,2,...,n} has the property that each pair of subsets has at least one element in common, then there are at most $2^{n-1}$ subsets in the ...
5
votes
5answers
122 views

Prove that $\sum_{k=0}^n \binom{3n-k}{2n}=\binom{3n+1}{n}$

Prove that $$\sum_{k=0}^n \binom{3n-k}{2n}=\binom{3n+1}{n}$$ I've tried multiple things that didn't work. Maybe this would help $$\sum_{k=0}^n \binom{3n-k}{2n}=\sum_{k=0}^n \binom{3n-(n-k)}{2n}=\...
1
vote
2answers
108 views

Combinatorial proof of $\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(l-k)^n=n!$, using inclusion-exclusion

If $l$ and $n$ are any positive integers, is there a proof of the identity $$\sum_{k=0}^{n}(-1)^{k}\binom{n}{k}(l-k)^n=n!\;$$ which uses the Inclusion-Exclusion Principle? (If necessary, ...
11
votes
2answers
469 views

Differentiating the binomial coefficient

I took a lecture in combinatorics this semester and the professor did the following step in a proof: He showed that function $f: x \mapsto \binom{x}{r}$ is convex for $x > r - 1$ (in order to use ...
5
votes
4answers
326 views

Sum of sum of binomial coefficients $\sum_{j=1}^{n}{\sum_{k=0}^{j}{{n}\choose{k}}}$

I know there is no simple way to solve the sum: $$\sum_{k=0}^{j}{{n}\choose{k}}$$ But what about the equation: $$\sum_{j=1}^{n}{\sum_{k=0}^{j}{{n}\choose{k}}}$$ Are there any simplifications or ...
0
votes
2answers
55 views

Asymptotics of $ f_c(n)=\sum_{k=0}^{\lfloor cn\rfloor}{n\choose k} $

Define $$ f_c(n)=\sum_{k=0}^{\lfloor cn\rfloor}{n\choose k} $$ for some fixed constant $c$ (say, $0<c<1/2$). What are the asymptotics of $f_c(n)$ as $n\to\infty$? It seems that this should be ...
0
votes
3answers
107 views

Alternating sum with binomial coefficients $\sum_{k=0}^{49}(-1)^k\binom{99}{2k}$

$$\sum_{k=0}^{49}(-1)^k\binom{99}{2k} = ?$$ I've tried expanding the binomial coefficient in its factorial form and can't seem to get to manipulate it in a way that solves the expression. $C_{99}^{...
6
votes
1answer
306 views

Sum of product of binomial coefficients and exponential function: $\sum^{n}_{k=0}2^k{{n+1}\choose k}{{r-n-2}\choose {n-k}}$

I would like to know how to obtain (if it exists) a closed form expression of the sum $$S=\sum^{n}_{k=0}2^k{{n+1}\choose k}{{r-n-2}\choose {n-k}}$$ So far, I have tried to use the method of ...
47
votes
2answers
4k views

Identity for convolution of central binomial coefficients: $\sum_{k=0}^n \binom{2k}{k}\binom{2(n-k)}{n-k}=2^{2n}$

It's not difficult to show that $$(1-z^2)^{-1/2}=\sum_{n=0}^\infty \binom{2n}{n}2^{-2n}z^{2n}$$ On the other hand, we have $(1-z^2)^{-1}=\sum z^{2n}$. Squaring the first power series and comparing ...